/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Z.YD
 * Date: 2025-07-22
 * Time: 18:19
 */
public class Leetcode {
        class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
     //反转链表
    public ListNode reverse(ListNode head) {
            if(head==null) return head;
            ListNode cur = head.next;
            head.next = null;
            while(cur!=null) {
                ListNode curN = cur.next;
                cur.next = head;
                head = cur;
                cur = curN;
            }
            return head;
    }
//求中间节点
    public ListNode middleNode(ListNode head) {
            if(head == null) return head;
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
    }
    //求倒数第k个节点
    public int  kthToLast(ListNode head ,int k) {
            if(head == null) return -1;
            if(k<=0) return -1;
            ListNode fast = head;
            ListNode slow = head;
            int count = 0;
            while(count != k-1) {
                fast= fast.next;
                if(fast == null) return -1;
                count++;
            }
            while(fast.next !=null) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow.val;
    }
    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//            递归方式实现
//            if(list1==null) return list2;
//            if(list2==null) return list1;
//            if(list1.val <= list2.val) {
//                list1.next = mergeTwoLists(list1.next,list2);
//                return list1;
//            } else {
//                list2.next = mergeTwoLists(list1,list2.next);
//                return list2;
//            }
        //非递归
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(list1!=null&&list2!=null) {
            if(list1.val<=list2.val) {
                cur.next = list1;
                list1= list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return head.next;
    }
}
